///////////////////////////////////////////////////////////////////////////
//
//  Crytek Engine Source File.
//  Copyright (C), Crytek Studios, 2002.
// -------------------------------------------------------------------------
//  File name:   brush.cpp
//  Version:     v1.00
//  Created:     8/7/2002 by Timur.
//  Compilers:   Visual Studio.NET
//  Description: 
// -------------------------------------------------------------------------
//  History: Based on Andrey's Indoor editor.
//	26/02/2010 Refactored by Jaesik.
//	09/04/2010 Implement a part of creating cone, cylinder, sphere are 
//						 added by Jaesik
//	12/04/2010 Implement merging by Jaesik.
//	21/04/2010 Implement CSG by Jaesik.
////////////////////////////////////////////////////////////////////////////

#include "StdAfx.h"
#include <IIndexedMesh.h>
#include "Brush.h"
#include "BrushFace.h"
#include "Objects\SubObjSelection.h"
#include "SolidBrushObject.h"
#include "Viewport.h"
#include "Settings.h"
#include "DisplaySettings.h"
#include "Grid.h"
#include "BrushPrimitive.h"
#include "BrushSerialize.h"
#include "Material\MaterialManager.h"

const float SBrush::VER_EPS							= 0.01f;
const float SBrush::VER_TIGHTEPS				= 0.0001f;
const float SBrush::BASIS_COPLANARPLANE	= 0.99999f;

const char* SBrushCommon::CSGOperationString[3] = { "Union", "Intersection", "Difference" };
SBrushCommon::VertexFaceIndexType SBrushCommon::VertexFaceMax = std::numeric_limits<SBrushCommon::VertexFaceIndexType>::max();

class CUndoBrush : public IUndoObject
{
public:
	CUndoBrush( SBrush* pBrush, const char *undoDescription )
	{
		assert( pBrush != 0 );
		if (undoDescription)
			m_undoDescription = undoDescription;
		else
			m_undoDescription = "SolidBrushUndo";
		m_undo = *pBrush;
		m_pBrush = pBrush;
	}

protected:

	virtual int GetSize()
	{
		return m_undo.GetMemorySize() + m_redo.GetMemorySize() + sizeof(CString);
	}

	virtual const char* GetDescription()
	{ 
		return m_undoDescription;
	};

	virtual void Undo( bool bUndo )
	{
		if (bUndo)
			m_redo = *m_pBrush;
		*m_pBrush = m_undo;
		m_pBrush->UpdateMesh();
	}

	virtual void Redo()
	{
		*m_pBrush = m_redo;
		m_pBrush->UpdateMesh();
		CBaseObject* object = GetIEditor()->GetSelectedObject();
		if( object->IsKindOf(RUNTIME_CLASS(CSolidBrushObject) ) )
		{
			CSolidBrushObject* solidObject = (CSolidBrushObject*)object;
			SBrush* pBrush = NULL;
			if( solidObject->GetBrush(pBrush) )
			{
				if( pBrush != m_pBrush )
					solidObject->SetBrush(m_pBrush);	
			}
		}
	}

private:

	CString m_undoDescription;
	_smart_ptr<SBrush> m_pBrush;
	SBrush m_undo;
	SBrush m_redo;
};


CEdGeometry* SBrush::Clone()
{
	SBrush* brush = new SBrush;	
	*brush = *this;
	brush->BuildBrush(false,false);
	return (CEdGeometry*)brush;
}

SBrush* SBrush::CreateBrush( CSolidBrushObject* obj )
{
	SBrush* brush = new SBrush;
	brush->SetOwner(obj);
	return brush;
}

bool SBrushSubSelection::AddPoint( Vec3 *pnt )
{
	if (std::find(points.begin(),points.end(),pnt) != points.end())
		return false;

	points.push_back(pnt);
	return true;
};


void SBrushSubSelection::Clear()
{
	points.clear();
}

SBrush::SBrush()
{
	m_nFlags = 0;
	m_pStatObj = 0;	
	m_Owner = NULL;

	m_bounds.Reset();

	m_selectionType = 0;
	m_isZeroTolerance = false;
}


SBrush::~SBrush()
{
	ClearFaces();
}


SBrush::SBrush( const SBrush& b )
{
	operator =( (const SBrush&)b );
}


// This operator is necessary for every single operation 
// because Sandbox is constantly doing an operation and undoing it whenever 
// you're editing an asset. And in order to do so, it creates and destroys 
// brushes all the time. 
// In order to keep information between creations and destructions, this  
// operator = is the key. Notice that this same operator is already called 
// as the copy constructor. 
SBrush& SBrush::operator = (const SBrush& b)
{
	ClearFaces();

	for( size_t i = 0; i < b.m_BrushVertices.size(); ++i )
	{
		m_BrushVertices.push_back( new SBrushVertex(*b.m_BrushVertices[i]) );
	}

	for( size_t i = 0; i < b.m_BrushFaces.size(); ++i )
	{
		m_BrushFaces.push_back( new SBrushFace(*b.m_BrushFaces[i]) );
	}

	for( size_t i = 0; i < b.m_BrushTriangles.size(); ++i )
	{
		m_BrushTriangles.push_back( new SBrushTriangle(*b.m_BrushTriangles[i]) );
	}

	m_bounds = b.GetBoundBox();
	m_nFlags = b.GetFlags();
	m_isZeroTolerance = b.GetZeroTolerance();

	return *this;
}


void SBrush::RecordUndo( const char *sUndoDescription )
{	
	if (CUndo::IsRecording())
	{
		CUndo::Record( new CUndoBrush(this,sUndoDescription) );
	}
}


void SBrush::Serialize( XmlNodeRef &xmlNode, bool bLoading, bool bUndo )
{
	CBrushSerialize Serializer;
	Serializer.Serialize( this, xmlNode, bLoading, bUndo );
}

bool SBrush::HitTest( HitContext &hit )
{
	if( !( (m_nFlags & BRF_SUB_OBJ_SEL) && GetEditModeFlag() ) 
	&& !(hit.nSubObjFlags & SO_HIT_NO_EDIT) ) 
	{	
		float dist = 0;
		SBrushFace* face = RayHit( hit.raySrc,hit.rayDir,&dist );
		if (face)
		{
			hit.dist = dist;
			return true;
		}
	}

	if(hit.nSubObjFlags & SO_HIT_NO_EDIT)
	{
		assert(hit.nSubObjFlags & SO_HIT_ELEM_FACE);
		assert(!(hit.nSubObjFlags & SO_HIT_ELEM_VERTEX));
		assert(!(hit.nSubObjFlags & SO_HIT_ELEM_EDGE));
		assert(!(hit.nSubObjFlags & SO_HIT_ELEM_POLYGON));
		m_selectionType = SO_ELEM_FACE;
	}

	// OS - Object Space, WS - World Space
	const Matrix34 &worldTM = m_matrix;
	Matrix34 invWorldTM		= worldTM.GetInverted();
	Vec3 vOSCameraPos			= invWorldTM.TransformPoint( hit.view->GetViewTM().GetTranslation() );
	Vec3 vWSCameraVector	= worldTM.GetTranslation() - hit.view->GetViewTM().GetTranslation();
	Vec3 vOSCameraVector	= invWorldTM.TransformVector(vWSCameraVector).GetNormalized();

	bool bSelectValue = !(hit.nSubObjFlags & SO_HIT_SELECT_REMOVE);
	bool bSelChanged = false;

	IUndoObject* pUndoObject = NULL;
	if( CUndo::IsRecording() && (hit.nSubObjFlags&SO_HIT_SELECT) )
	{
		pUndoObject = new CUndoBrush( this, "Brush, HitTest"  );
	}

	if ( (hit.nSubObjFlags & SO_HIT_SELECT) && 
			!(hit.nSubObjFlags & SO_HIT_SELECT_ADD) && 
			!(hit.nSubObjFlags & SO_HIT_SELECT_REMOVE) )
	{
		bSelChanged = ClearSelection();
	}

	if (m_selectionType == SO_ELEM_VERTEX)
	{
		bSelChanged = SelectVertex( hit, vOSCameraPos, worldTM );
	}
	else if (m_selectionType == SO_ELEM_EDGE)
	{
		bSelChanged = SelectEdge( hit, vOSCameraVector, worldTM );
	}
	else if (m_selectionType == SO_ELEM_FACE || m_selectionType == SO_ELEM_POLYGON)
	{
		bSelChanged = SelectFace( hit, vOSCameraVector, worldTM );
	}

	if( pUndoObject && bSelChanged )
	{
		CUndo::Record( pUndoObject );
	}
	else
	{
		if( pUndoObject )
			pUndoObject->Release();
	}

	return bSelChanged;
}


bool SBrush::SelectVertex( HitContext& hit, const Vec3& osCameraPos, const Matrix34& worldTM )
{
	bool bSelChanged = false;
	bool bSelectValue = !(hit.nSubObjFlags & SO_HIT_SELECT_REMOVE);

	for( size_t i = 0; i < m_BrushFaces.size(); ++i)
	{
		SBrushFace *face = m_BrushFaces[i];

		for( size_t k = 0; k < face->pointindexlist.size(); ++k )
		{
			SBrushVertex* vert = m_BrushVertices[face->pointindexlist[k]];

			if (g_SubObjSelOptions.bIgnoreBackfacing && (vert->pos-osCameraPos).dot(face->plane.normal) > 0)
				continue;

			CPoint p = hit.view->WorldToView( worldTM.TransformPoint(vert->pos) );
			if (p.x >= hit.rect.left && p.x <= hit.rect.right && p.y >= hit.rect.top && p.y <= hit.rect.bottom)
			{
				if( !( hit.nSubObjFlags & SO_HIT_SELECT ) )
				{
					if ( !(hit.nSubObjFlags & SO_HIT_TEST_SELECTED) )
						return true;
					else if (vert->bSelected)
						return true;
				}
				else
				{
					if( vert->bSelected != bSelectValue )
					{
						bSelChanged = true;
						vert->bSelected = bSelectValue;
					}
				}
			}
		}
	}
	return bSelChanged;
}


bool SBrush::SelectEdge( HitContext& hit, const Vec3& osCameraDir, const Matrix34& worldTM )
{
	bool bSelChanged = false;
	bool bSelectValue = !(hit.nSubObjFlags & SO_HIT_SELECT_REMOVE);

	for( size_t k = 0; k < m_BrushFaces.size(); ++k )
	{
		SBrushFace * f = m_BrushFaces[k];
		int edgesize = GetNumberOfFaceEdges(f);

		if( g_SubObjSelOptions.bIgnoreBackfacing && osCameraDir.Dot(f->plane.normal) > 0 )
		{
			continue;
		}

		for( int i = 0; i < edgesize; ++i )	
		{
			int firstVtxIdx = 0;
			int secondVtxIdx = 0;

			f->MapEdgeIndexToPolyIndices( m_BrushVertices, m_BrushTriangles, i, firstVtxIdx, secondVtxIdx );

			const SBrushVertex* v0 = m_BrushVertices[f->pointindexlist[firstVtxIdx]];
			const SBrushVertex* v1 = m_BrushVertices[f->pointindexlist[secondVtxIdx]];

			Vec3 wv0 = worldTM.TransformPoint(v0->pos);
			Vec3 wv1 = worldTM.TransformPoint(v1->pos);

			if( !(hit.nSubObjFlags & SO_HIT_SELECT) )
			{
				if( !(hit.nSubObjFlags & SO_HIT_TEST_SELECTED) )
				{
					return hit.view->HitTestLine( wv0, wv1, hit.point2d, 5 );
				}
				else if( f->selectededge&(1<<i))
				{
					return hit.view->HitTestLine( wv0, wv1, hit.point2d, 5 );
				}
			} 
			else if( hit.nSubObjFlags & SO_HIT_POINT )
			{
				if( hit.view->HitTestLine( wv0, wv1, hit.point2d, 5 ) )
				{
					bool bSelected = (f->selectededge&(1<<i)) ? true : false;
					if( bSelected != bSelectValue )
					{
						bSelChanged = true;
						f->selectededge |= (1<<i);
						m_BrushVertices[f->pointindexlist[firstVtxIdx]]->bSelected	= true;
						m_BrushVertices[f->pointindexlist[secondVtxIdx]]->bSelected	= true;
					}
				}
			}
			else
			{
				Vec3 mid = wv0 + ( wv1 - wv0 ) * 0.5f;
				CPoint stViewPoint = hit.view->WorldToView(mid);

				if( stViewPoint.x >= hit.rect.left && 
						stViewPoint.x <= hit.rect.right && 
						stViewPoint.y >= hit.rect.top && 
						stViewPoint.y <= hit.rect.bottom )
				{
					bool bSelected = (f->selectededge&(1<<i)) ? true : false;
					if( bSelected != bSelectValue )
					{
						bSelChanged = true;
						f->selectededge |= (1<<i);
						m_BrushVertices[firstVtxIdx]->bSelected		= true;
						m_BrushVertices[secondVtxIdx]->bSelected	= true;
					}
				}
			}
		}
	}

	return bSelChanged;
}


bool SBrush::SelectFace( HitContext& hit, const Vec3& osCameraDir, const Matrix34& worldTM )
{
	bool bSelectValue = !(hit.nSubObjFlags & SO_HIT_SELECT_REMOVE);
	SBrushFace * pHitFace = RayHit( hit.raySrc, hit.rayDir, &hit.dist );

	if( !(hit.nSubObjFlags&SO_HIT_SELECT) )
	{
		if( pHitFace )
		{
			if (!(hit.nSubObjFlags & SO_HIT_TEST_SELECTED) )
				return true;
			else if (pHitFace->bSelected)
				return true;
		}
	}
	else if( hit.nSubObjFlags & SO_HIT_POINT )
	{
		if( pHitFace && pHitFace->bSelected != bSelectValue )
		{
			pHitFace->bSelected = bSelectValue;
			return true;
		}
	}
	else
	{
		for (int i = 0; i < m_BrushFaces.size(); ++i)
		{
			SBrushFace * face = m_BrushFaces[i];

			if (g_SubObjSelOptions.bIgnoreBackfacing && osCameraDir.Dot(face->plane.normal) > 0)
				continue; 

			face->CalcCenter(m_BrushVertices);
			CPoint p = hit.view->WorldToView( worldTM.TransformPoint(face->center) );
			if( p.x >= hit.rect.left && p.x <= hit.rect.right && p.y >= hit.rect.top && p.y <= hit.rect.bottom &&
				face->bSelected != bSelectValue )
			{
				face->bSelected = bSelectValue;
				return true;
			}
		}
	}

	return false;
}


void SBrush::ModifySelection( SSubObjSelectionModifyContext &modCtx, bool isUndo )
{
	if( !m_isZeroTolerance && ( m_selectionType == SO_ELEM_VERTEX || m_selectionType == SO_ELEM_EDGE || m_selectionType == SO_ELEM_FACE))
		m_isZeroTolerance = true;

	Matrix34 worldTM = m_matrix;
	Matrix34 invTM = worldTM.GetInverted();
	Matrix34 modRefFrame = invTM * modCtx.worldRefFrame;
	Matrix34 modRefFrameInverse = modCtx.worldRefFrame.GetInverted() * worldTM;

	if (modCtx.type == SO_MODIFY_MOVE)
	{
		Vec3 vOffset = modCtx.vValue;
		vOffset = modCtx.worldRefFrame.GetInverted().TransformVector(vOffset);
		Matrix34 tm = modRefFrame * Matrix34::CreateTranslationMat(vOffset) * modRefFrameInverse;

		if( m_selectionType == SO_ELEM_VERTEX )
		{
			for( size_t i = 0; i < m_BrushVertices.size(); ++i )
			{
				SBrushVertex* v = m_BrushVertices[i];
				if( v->bSelected == true )
				{
					v->pos = tm.TransformPoint( v->pos );
					v->pos = invTM * modCtx.view->SnapToGrid( worldTM * v->pos );
				}
			}

			ComputeFacePlanes();
			ComputeTexCoord();
			ComputeBoundBox();
			Invalidate();
		}
		else if( m_selectionType == SO_ELEM_EDGE )
		{
			std::set<SBrushCommon::VertexFaceIndexType> vlist;

			for( size_t i = 0; i < m_BrushVertices.size(); ++i )
			{
				SBrushVertex* vi = m_BrushVertices[i];

				if( vi->bSelected == false )
					continue;
				
				for( size_t k = 0; k < m_BrushVertices.size(); ++k )
				{
					SBrushVertex* vk = m_BrushVertices[k];

					if( i == k )
						continue;

					if( vk->bSelected == true )
						continue;

					if( vi->pos.IsEquivalent(vk->pos,VER_EPS) )
						vlist.insert(k);
				}
			}

			for( size_t i = 0; i < m_BrushVertices.size(); ++i )
			{
				SBrushVertex* v = m_BrushVertices[i];
				if( v->bSelected == true )
				{
					v->pos = tm.TransformPoint( v->pos );
					v->pos = invTM * modCtx.view->SnapToGrid( worldTM * v->pos );
				}
			}

			std::set<SBrushCommon::VertexFaceIndexType>::iterator ii = vlist.begin();
			for( ; ii != vlist.end(); ++ii )
			{
				SBrushVertex* v = m_BrushVertices[*ii];
				v->pos = tm.TransformPoint( v->pos );
				v->pos = invTM * modCtx.view->SnapToGrid( worldTM * v->pos );
			}

			ComputeFacePlanes();
			ComputeTexCoord();
			ComputeBoundBox();
			Invalidate();
		}
		else if( m_selectionType == SO_ELEM_FACE || m_selectionType == SO_ELEM_POLYGON )
		{
			for(size_t i = 0; i < m_BrushFaces.size(); ++i)
			{
				SBrushFace * face = m_BrushFaces[i];
				if( face->bSelected )
				{
					std::vector<Vec3*> ptlist;

					// I think this part should need to be optimized using KD-Tree or OCTree
					for( size_t j = 0; j < m_BrushVertices.size(); ++j )
					{
						SBrushVertex* v = m_BrushVertices[j];
						
						for( size_t k = 0; k < face->pointindexlist.size(); ++k )
						{
							if( std::find( face->pointindexlist.begin(), face->pointindexlist.end(), j ) != face->pointindexlist.end() )
								continue;
							if( m_BrushVertices[face->pointindexlist[k]]->pos.IsEquivalent( v->pos ) )
							{
								ptlist.push_back(&v->pos);
							}
						}
					}

					for( size_t j = 0; j < face->pointindexlist.size(); ++j )
					{
						m_BrushVertices[face->pointindexlist[j]]->pos = tm.TransformPoint( m_BrushVertices[face->pointindexlist[j]]->pos );
					}

					for( size_t j = 0; j < ptlist.size(); ++j )
					{
						*ptlist[j] = tm.TransformPoint( *ptlist[j] );
					}
				}
			}

			ComputeFacePlanes();
			ComputeTexCoord();
			ComputeBoundBox();
			Invalidate();
		}
	}

	SetModified();
}



Vec3 SBrush::CalcNormal( const Vec3& v0, const Vec3& v1, const Vec3& v2 ) const
{
	Vec3 n = (v2-v1)^(v0-v1);
	n.Normalize();
	return n;
}


bool SBrush::BuildBrush(	bool bComputeAdjacentTriangle, 
													bool bComputeCoplanarTriangle, 
													bool bComputeTexCoord, 
													bool bComputeBoundBox )
{
	Invalidate();

	if( bComputeAdjacentTriangle )
	{
		ComputeAdjacentTriangle();
		if( bComputeCoplanarTriangle )
			ComputeCoplanarTriangle();
	}

	if( bComputeTexCoord )
		ComputeTexCoord();

	if( bComputeBoundBox )
		ComputeBoundBox();

	return true;
}



void SBrush::RecalcTexCoords()
{
	Invalidate();

	for( size_t i = 0; i < m_BrushFaces.size(); ++i)
	{
		SBrushFace * f = m_BrushFaces[i];
		int numPts = f->pointindexlist.size();
		for( int j = 0; j < numPts; ++j )
		{
			f->CalcTexCoords( *m_BrushVertices[f->pointindexlist[j]] );
		}
	}
}


void SBrush::ComputeTexCoord()
{
	std::vector<SBrushFace*>::iterator ibf = m_BrushFaces.begin();
	for( ; ibf != m_BrushFaces.end(); ++ibf)
	{
		SBrushFace *f = *ibf;
		for( size_t i=0; i < f->pointindexlist.size(); ++i )
			f->CalcTexCoords( *m_BrushVertices[f->pointindexlist[i]] );
	}
}


bool SBrush::ComputeBoundBox()
{
	AABB box;
	box.Reset();

	std::vector<SBrushVertex*>::iterator ibv = m_BrushVertices.begin();
	for( ; ibv != m_BrushVertices.end(); ++ibv )
	{
		SBrushVertex *v = *ibv;
		box.Add( v->pos );
	}

	if(	box.min.x > box.max.x ||
		box.min.y > box.max.y ||
		box.min.z > box.max.z)
	{
		m_bounds.min = m_bounds.max = Vec3(0,0,0);
		return false;
	}

	m_bounds = box;

	if( m_Owner )
		m_Owner->UpdateBoundBox();

	return true;
}


void SBrush::ComputeAdjacentTriangle()
{
	const int NumberOfTriangleEdge = 3;
	const int NumberOfEdgeVertex = 2;

	size_t trisize = m_BrushTriangles.size();

	for( size_t i = 0; i < trisize; ++i )
	{
		SBrushTriangle* basetri = m_BrushTriangles[i];

		Vec3 baseedge[NumberOfTriangleEdge][NumberOfEdgeVertex] = 
								{	{ m_BrushVertices[basetri->vertexindices[0]]->pos, m_BrushVertices[basetri->vertexindices[1]]->pos },
									{ m_BrushVertices[basetri->vertexindices[1]]->pos, m_BrushVertices[basetri->vertexindices[2]]->pos },
									{ m_BrushVertices[basetri->vertexindices[2]]->pos, m_BrushVertices[basetri->vertexindices[0]]->pos } };

		for( int a = 0; a < NumberOfTriangleEdge; ++a )
		{
			for( int k = 0; k < trisize; ++k )
			{
				if( i == k )
					continue;

				SBrushTriangle* othertri = m_BrushTriangles[k];

				Vec3 otheredge[NumberOfTriangleEdge][NumberOfEdgeVertex] = 
										{{ m_BrushVertices[othertri->vertexindices[1]]->pos, m_BrushVertices[othertri->vertexindices[0]]->pos },
										 { m_BrushVertices[othertri->vertexindices[2]]->pos, m_BrushVertices[othertri->vertexindices[1]]->pos },
										 { m_BrushVertices[othertri->vertexindices[0]]->pos, m_BrushVertices[othertri->vertexindices[2]]->pos } };

				bool bFindEdge = false;

				for( int b = 0; b < NumberOfTriangleEdge; ++b )
				{
					if( baseedge[a][0].IsEquivalent(otheredge[b][0],VER_EPS) && baseedge[a][1].IsEquivalent(otheredge[b][1],VER_EPS) )
					{
						basetri->adjacentfidx[a] = k;
						bFindEdge = true;
						break;
					}
				}

				if( bFindEdge == true )
					break;
			}
		}
	}
}


void SBrush::ComputeCoplanarTriangle()
{
	size_t trisize = m_BrushTriangles.size();

	for( int i = 0; i < trisize; ++i )
	{
		m_BrushTriangles[i]->faceidx = SBrushCommon::VertexFaceMax;
	}

	std::vector<SBrushFace*>::iterator ibf = m_BrushFaces.begin();
	for( ; ibf != m_BrushFaces.end(); ++ibf )
	{
		delete *ibf;
	}
	m_BrushFaces.clear();

	for( int i = 0; i < trisize; ++i )
	{
		if( m_BrushTriangles[i]->faceidx != SBrushCommon::VertexFaceMax )
			continue;

		SBrushTriangle* tri = m_BrushTriangles[i];
		tri->faceidx = (SBrushCommon::VertexFaceIndexType)m_BrushFaces.size();

		SBrushFace* face = new SBrushFace;

		face->pointindexlist.push_back(tri->vertexindices[0]);
		face->pointindexlist.push_back(tri->vertexindices[1]);
		face->pointindexlist.push_back(tri->vertexindices[2]);
		face->triangleidxlist.push_back(i);

		ComputeAdjacentCoplanar(i,face,tri->faceidx);
		
		m_BrushFaces.push_back(face);
	}

	ComputeFacePlanes();
}


void SBrush::ComputeAdjacentCoplanar( int current, SBrushFace* face, SBrushCommon::VertexFaceIndexType faceidx )
{	
	SBrushTriangle* currentt = m_BrushTriangles[current];

	for( int i = 0; i < 3; ++i )
	{
		SBrushCommon::VertexFaceIndexType adjacent = currentt->adjacentfidx[i];

		if( adjacent == SBrushCommon::VertexFaceMax )
			continue;

		SBrushTriangle* adjacentt = m_BrushTriangles[adjacent];

		if( adjacentt->faceidx != SBrushCommon::VertexFaceMax )
			continue;

		float difference = currentt->normal.Dot(adjacentt->normal);
		if( difference >= BASIS_COPLANARPLANE )
		{
			face->triangleidxlist.push_back(adjacent);

			for( int k = 0; k < 3; ++k )
			{
				if( adjacentt->vertexindices[k] != currentt->vertexindices[i] && 
						adjacentt->vertexindices[k] != currentt->vertexindices[(i+1)%3] )
				{
					std::vector<SBrushCommon::VertexFaceIndexType>::iterator ip = std::find(	face->pointindexlist.begin(), 
																																							face->pointindexlist.end(), 
																																							currentt->vertexindices[i] );
					face->pointindexlist.insert( ip+1, adjacentt->vertexindices[k] );
				}
			}
			adjacentt->faceidx = faceidx;
			ComputeAdjacentCoplanar(adjacent,face,faceidx);
		}
	}
}


void SBrush::Move( Vec3& delta )
{
	size_t vsize = m_BrushVertices.size();
	SBrush backup = *this;

	for( int i = 0; i < vsize; ++i )
	{
		SBrushVertex* v = m_BrushVertices[i];
		v->pos += delta;
	}

	if( IsValid() == false )
	{
		*this = backup;
	}
	else
	{
		Invalidate();
	}
}


void SBrush::Transform( const Matrix34 &tm, bool bUndo )
{
	if( bUndo )
		RecordUndo( "Brush Transform");

	size_t vsize = m_BrushVertices.size();	
	for( int i = 0; i < vsize; ++i )
	{
		SBrushVertex* v = m_BrushVertices[i];
		v->pos = tm.TransformPoint(v->pos);
	}

	ComputeFacePlanes();
	ComputeBoundBox();
	ComputeTexCoord();

	Invalidate();
}


void SBrush::SnapToGrid( bool bOnlySelected )
{
	if( bOnlySelected && m_selectionType != SO_ELEM_VERTEX )
		return;

	SBrush backup = *this;	

	size_t vsize = m_BrushVertices.size();

	for( int i = 0; i < vsize; ++i )
	{
		SBrushVertex* bv = m_BrushVertices[i];

		if( bOnlySelected && !bv->bSelected )
			continue;

		bv->pos = gSettings.pGrid->Snap( bv->pos );
	}

	if( IsValid() == false )
	{
		*this = backup;
	}
	else
	{
		Invalidate();
	}
}


void SBrush::SelectSide( Vec3 Origin, Vec3 Dir,bool shear,SBrushSubSelection &subSelection )
{
}


void SBrush::GenerateIndexMesh(IIndexedMesh* pMesh)
{	
	if (pMesh == NULL)
		return;

	const size_t numVerts = m_BrushVertices.size();
	const size_t numTriangles = m_BrushTriangles.size();

	pMesh->SetVertexCount(numVerts);
	pMesh->SetFacesCount(numTriangles);
	pMesh->SetTexCoordsCount(numVerts);

	Vec3* const positions = pMesh->GetMesh()->GetStreamPtr<Vec3>(CMesh::POSITIONS);
	Vec3* const normals = pMesh->GetMesh()->GetStreamPtr<Vec3>(CMesh::NORMALS);
	SMeshTexCoord* const texcoords = pMesh->GetMesh()->GetStreamPtr<SMeshTexCoord>(CMesh::TEXCOORDS);
	SMeshFace* const faces = pMesh->GetMesh()->GetStreamPtr<SMeshFace>(CMesh::FACES);

	for(int i = 0; i < numVerts; ++i)
	{
		const SBrushVertex* const v = m_BrushVertices[i];
		positions[i] = v->pos;
		texcoords[i].s = v->st[0];
		texcoords[i].t = v->st[1];
	}

	int nMaxMatId = 0;

	for (int i = 0; i < numTriangles; ++i)
	{
		const SBrushTriangle* const bt = m_BrushTriangles[i];
		SMeshFace* const mf = &faces[i];

		mf->v[0] = mf->t[0] = bt->vertexindices[0];
		mf->v[1] = mf->t[1] = bt->vertexindices[1];
		mf->v[2] = mf->t[2] = bt->vertexindices[2];

		normals[bt->vertexindices[0]] = bt->normal;
		normals[bt->vertexindices[1]] = bt->normal;
		normals[bt->vertexindices[2]] = bt->normal;

		const short matID = m_BrushFaces[bt->faceidx]->matID;
		mf->nSubset = matID;
		if (matID > nMaxMatId)		
			nMaxMatId = matID;
		mf->dwFlags = 0;
	}

	pMesh->SetSubSetCount(nMaxMatId + 1);
	for (int i = 0; i < nMaxMatId + 1; ++i)
		pMesh->SetSubsetMaterialId(i, i);

	pMesh->CalcBBox();
}

void SBrush::OptimizeMesh( IIndexedMesh* pMesh )
{
	pMesh->Optimize();
	pMesh->RestoreFacesFromIndices();
}

void SBrush::FitTexture(int nX, int nY)
{
	size_t fsize = m_BrushFaces.size();
	for( int i = 0; i < fsize; ++i)
		m_BrushFaces[i]->FitTexture(m_BrushVertices, nX, nY);	
}


bool SBrush::ClearSelection()
{
	bool bSelChanged = false;

	std::vector<SBrushFace*>::iterator iface = m_BrushFaces.begin();
	for(;iface!=m_BrushFaces.end();++iface)
	{
		SBrushFace* face = *iface;
		if( face->bSelected == true )
		{
			face->bSelected = false;
			bSelChanged = true;
		}

		if( face->selectededge )
		{
			face->selectededge = 0;
			bSelChanged = true;
		}
	}

	std::vector<SBrushVertex*>::iterator ivertex = m_BrushVertices.begin();
	for(;ivertex!=m_BrushVertices.end();++ivertex)
	{
		SBrushVertex* vertex = *ivertex;
		if( vertex->bSelected == true )
		{
			vertex->bSelected = false;
			bSelChanged = true;
		}
	}

	return bSelChanged;
}


void SBrush::Selection_SnapToGrid()
{
	RecordUndo( "Brush SnapToGrid");
	SnapToGrid(true);
}


void SBrush::Selection_SetMatId( int nMatId )
{
	if( !( m_selectionType == SO_ELEM_FACE || m_selectionType == SO_ELEM_POLYGON ) )
		return;

	RecordUndo("Brush Set Material ID");

	for( int i = 0; i < m_BrushFaces.size(); ++i)
	{
		SBrushFace  * face = m_BrushFaces[i];
		if (face->bSelected)
		{
			face->matID = nMatId;
		}
	}
}


void SBrush::Selection_SelectMatId( int nMatId )
{
	if (m_selectionType == SO_ELEM_VERTEX)
	{
		RecordUndo( "Brush, Select Material ID by vertex");
		ClearSelection();

		for (int i = 0; i < m_BrushFaces.size(); ++i)
		{
			SBrushFace * face = m_BrushFaces[i];
			if (face->matID == nMatId)
			{
				for( size_t j = 0; j < face->pointindexlist.size(); ++j )
				{
					m_BrushVertices[face->pointindexlist[j]]->bSelected = true;
				}
			}
		}
	}
	else if (m_selectionType == SO_HIT_ELEM_EDGE)
	{
		RecordUndo( "Brush, Select Material ID by Edge");
		ClearSelection();

		int nNumberOfFaces(m_BrushFaces.size());
		int nCurrentFace(0);
		int nCurrentEdge(0);

		for( nCurrentFace = 0; nCurrentFace < nNumberOfFaces; ++nCurrentFace )
		{
			SBrushFace * face = m_BrushFaces[nCurrentFace];
			if (face->matID == nMatId )
			{
				for (nCurrentEdge=0;nCurrentEdge < GetNumberOfFaceEdges(face);++nCurrentEdge)
				{
					face->selectededge |= (1<<nCurrentEdge);
				}
			}
		}
	}
	else if(	m_selectionType == SO_ELEM_FACE || 
						m_selectionType == SO_ELEM_POLYGON)
	{	
		RecordUndo( "Brush, Select Material ID by Face");
		ClearSelection();

		for (int i = 0; i < m_BrushFaces.size(); ++i)
		{
			SBrushFace * face = m_BrushFaces[i];
			if (face->matID == nMatId )
			{
				face->bSelected = true;
			}
		}
	}
}

void SBrush::ClearFaces()
{
	std::vector<SBrushVertex*>::iterator iv = m_BrushVertices.begin();
	for( ; iv != m_BrushVertices.end(); ++iv )
	{
		assert(*iv);
		delete *iv;
	}
	m_BrushVertices.clear();

	std::vector<SBrushFace*>::iterator iface = m_BrushFaces.begin();
	for( ; iface != m_BrushFaces.end(); ++iface )
	{
		assert(*iface);
		delete *iface;
	}
	m_BrushFaces.clear();

	std::vector<SBrushTriangle*>::iterator itri = m_BrushTriangles.begin();
	for( ; itri != m_BrushTriangles.end(); ++itri )
	{
		assert(*itri);
		delete *itri;
	}
	m_BrushTriangles.clear();
}


bool SBrush::Clone( _smart_ptr<SBrush>& brush )
{
	brush = new SBrush;
	*brush = *this;
	return true;
}


void SBrush::ComputeFacePlanes()
{
	std::vector<SBrushFace*>::iterator ii = m_BrushFaces.begin();

	for( ; ii != m_BrushFaces.end(); ++ii )
	{
		SBrushFace* f = *ii;
		SBrushCommon::VertexFaceIndexType tindex[3] = { 0,1,2 };
		std::vector<Vec3> vlist;
		for( int i = 0; i < f->pointindexlist.size(); ++i )
			vlist.push_back(m_BrushVertices[f->pointindexlist[i]]->pos);
		bool bSuccess = FindTrianglePointsInPolygonForFace( vlist, tindex[0], tindex[1], tindex[2] );
		assert(bSuccess);
		f->MakePlane(m_BrushVertices,tindex[0],tindex[1],tindex[2]);
	}
}


SBrushFace* SBrush::RayHit( Vec3 rayOrigin, Vec3 rayDir, float *dist ) const
{
	for( size_t i = 0; i < m_BrushFaces.size(); ++i )
	{
		SBrushFace* brushface = m_BrushFaces[i];

		if( brushface->plane.normal.Dot(rayDir) > 0 )
			continue;

		for( size_t k = 0; k < brushface->triangleidxlist.size(); ++k )
		{
			SBrushTriangle* brushTri = m_BrushTriangles[brushface->triangleidxlist[k]];

			Vec3 v0 = m_BrushVertices[brushTri->vertexindices[0]]->pos;
			Vec3 v1 = m_BrushVertices[brushTri->vertexindices[1]]->pos;
			Vec3 v2 = m_BrushVertices[brushTri->vertexindices[2]]->pos;

			Vec3 e1 = v1-v0;
			Vec3 e2 = v2-v0;

			Vec3 dd = rayDir;
			Vec3 p = dd.cross( e2 );

			float det = e1.dot( p );

			if( det > -VER_EPS && det < VER_EPS )
				continue;

			float	invDet = 1.0f / det;
			Vec3	s = rayOrigin - v0;
			float	u = s.dot( p ) * invDet;

			if( u < 0.f || u > 1.f )
				continue;

			Vec3	q = s.cross( e1 );
			float	v = dd.dot( q ) * invDet;

 			if( v < 0.f || (u + v) > 1.f )
 				continue;

			*dist = e2.dot( q ) * invDet;

			return brushface;
		}
	}

	return NULL;
}


bool SBrush::IsValid() const
{
	size_t tsize = m_BrushTriangles.size();
	for( int i = 0; i < tsize; ++i )
	{
		SBrushTriangle* t = m_BrushTriangles[i];

		const Vec3& v0 = m_BrushVertices[t->vertexindices[0]]->pos;
		const Vec3& v1 = m_BrushVertices[t->vertexindices[1]]->pos;
		const Vec3& v2 = m_BrushVertices[t->vertexindices[2]]->pos;

		if( ((v0-v1)^(v2-v1)).GetLength() < VEC_EPSILON )
			return false;
	}
	return true;
}


int SBrush::GetMemorySize()
{
	int size = 0;

	for( size_t i = 0; i < m_BrushTriangles.size(); ++i )
	{
		size += m_BrushTriangles[i]->GetMemorySize();
	}

	for( size_t i = 0; i < m_BrushVertices.size(); ++i )
	{
		size += m_BrushVertices[i]->GetMemorySize();
	}

	for( size_t i = 0; i < m_BrushFaces.size(); ++i )
	{
		size += m_BrushFaces[i]->GetMemorySize();
	}

	return size;
}


bool SBrush::UpdateMesh()
{
	Invalidate();

	if( IsFaceListEmpty() )
		return false;

	ExcludeInvalidData();

	if(m_pStatObj)
	{
		m_pStatObj->Release();
		m_pStatObj = NULL;
	}

	m_pStatObj = GetIEditor()->Get3DEngine()->CreateStatObj();
	m_pStatObj->AddRef();

	m_nFlags |= BRF_MESH_VALID;

	IMaterial* pMaterial = NULL;

	if( m_Owner )
	{
		CMaterial* pObjMaterial = m_Owner->GetMaterial();
		if( pObjMaterial )
			pMaterial = pObjMaterial->GetMatInfo();
	}
	
	if( pMaterial == NULL && m_Owner)
	{
		m_Owner->SetMaterial(CSolidBrushObject::GetSolidDefaultMaterialName());
		if( m_Owner->GetMaterial() )
			pMaterial = m_Owner->GetMaterial()->GetMatInfo();
	}

	// lightshapes don't have an owner
	if (pMaterial == NULL)
	{
		pMaterial = gEnv->p3DEngine->GetMaterialManager()->LoadMaterial(CSolidBrushObject::GetSolidDefaultMaterialName());
	}

	m_pStatObj->SetMaterial(pMaterial);
	IIndexedMesh *pMesh = m_pStatObj->GetIndexedMesh();
	GenerateIndexMesh(pMesh);
	OptimizeMesh(pMesh);

	m_pStatObj->Invalidate(true, m_isZeroTolerance ? 0.0f : 0.05f);

	return m_nFlags & BRF_MESH_VALID;
}


bool SBrush::GetIStatObj( IStatObj*& pOutStatObj )
{
	if (!m_pStatObj || !(m_nFlags&BRF_MESH_VALID))
		UpdateMesh();

	pOutStatObj = m_pStatObj;

	return m_pStatObj && (m_nFlags&BRF_MESH_VALID);
}


IIndexedMesh* SBrush::GetIndexedMesh()
{
	IStatObj *pObj = NULL;	
	if( GetIStatObj(pObj) )
		return pObj->GetIndexedMesh();
	return 0;
}


void SBrush::SetModified( bool bModified )
{
	if (bModified)
		m_nFlags |= BRF_MODIFIED;
	else
		m_nFlags &= ~BRF_MODIFIED;
}


bool SBrush::StartSubObjSelection( const Matrix34 &nodeWorldTM,int elemType,int nFlags )
{
	GetEditModeFlag()=true;
	m_nFlags |= BRF_SUB_OBJ_SEL;
	m_selectionType = elemType;
	return true;
}


void SBrush::EndSubObjSelection()
{
	GetEditModeFlag()=false;

	m_nFlags &= ~BRF_SUB_OBJ_SEL;

	if (m_pStatObj)
	{
		int nStatObjFlags = m_pStatObj->GetFlags();
		nStatObjFlags &= ~STATIC_OBJECT_HIDDEN;
		m_pStatObj->SetFlags( nStatObjFlags );
	}
}

AABB SBrush::GetWorldBound() const
{
	AABB aabb;
	aabb.Reset();

	for( size_t i = 0; i < m_BrushVertices.size(); ++i )
	{
		Vec3 worldpts = m_matrix * m_BrushVertices[i]->pos;
		aabb.Add(worldpts);
	}

	return aabb;
}


size_t SBrush::GetNumberOfFaceEdges( SBrushFace* face ) const
{
	return face->triangleidxlist.size() * 3;
}


size_t SBrush::GetNumberOfFaces() const
{	
	return m_BrushFaces.size();
}


size_t SBrush::GetNumberOfTriangles() const
{
	return m_BrushTriangles.size();
}


const Vec3& SBrush::GetFaceNormal( int idx ) const
{	
	return m_BrushFaces[idx]->plane.normal;
}

float SBrush::GetFaceDistance( int idx ) const
{	
	return m_BrushFaces[idx]->plane.distance;
}

size_t SBrush::GetNumberOfFacePoints( int idx )	const
{	
	return m_BrushFaces[idx]->pointindexlist.size();
}


const Vec3& SBrush::GetFacePointPos( int idx, int vidx ) const
{	
	return m_BrushVertices[m_BrushFaces[idx]->pointindexlist[vidx]]->pos;
}


bool SBrush::IsValidFace( int idx ) const
{	
	return	idx >= 0 && idx < m_BrushFaces.size() && 
					!m_BrushFaces[idx]->pointindexlist.empty() && 
					!m_BrushFaces[idx]->triangleidxlist.empty();	
}


bool SBrush::IsPointSelected( int idx, int vidx ) const
{	
	return m_BrushVertices[m_BrushFaces[idx]->pointindexlist[vidx]]->bSelected;
}


bool SBrush::IsFaceSelected( int idx ) const
{	
	return m_BrushFaces[idx]->bSelected;
}


void SBrush::SetFaceSelected( int idx, bool bSelected ) const
{	
	m_BrushFaces[idx]->bSelected = bSelected;
}


size_t SBrush::GetNumberOfFaceEdges( int idx ) const
{	
	return GetNumberOfFaceEdges(m_BrushFaces[idx]);
}


int SBrush::GetFaceSelectedEdge( int idx ) const
{	
	return m_BrushFaces[idx]->selectededge;
}


const Vec3& SBrush::GetFaceCenter( int idx ) const
{	
	return m_BrushFaces[idx]->GetCenter();
}


void SBrush::CalculateFaceCenter( int idx ) const
{	
	m_BrushFaces[idx]->CalcCenter(m_BrushVertices);
}

void SBrush::CalculateFaceTextureBasis( int idx, Vec3& tu, Vec3& tv) const
{
	SBrushFace::CalcTextureBasis(	m_BrushFaces[idx]->plane,
		m_BrushFaces[idx]->texinfo,
		tu,tv);
}


void SBrush::CalculateFaceBound( int idx, Vec3& mins, Vec3& maxs ) const
{	
	m_BrushFaces[idx]->CalcBound(m_BrushVertices, mins, maxs);
}


const SBrushCommon::STexInfo& SBrush::GetFaceTexInfo( int idx ) const
{
	return m_BrushFaces[idx]->texinfo;
}

void SBrush::SetFaceTexInfo( int idx, const SBrushCommon::STexInfo& ti )	const
{
	m_BrushFaces[idx]->texinfo = ti;
}

int	SBrush::GetFaceMaterialID( int idx ) const
{	
	return m_BrushFaces[idx]->matID;
}

void SBrush::SetFaceMaterialID( int idx, int matID )	const
{	
	m_BrushFaces[idx]->matID = matID;
}

void SBrush::FitFaceTexture( int idx, float fTileU, float fTileV ) const
{
	m_BrushFaces[idx]->FitTexture(m_BrushVertices,fTileU,fTileV);
}

void SBrush::MapEdgeIndexToPolyIndices( int idx, const int& nEdgeIndex, int &rnFirstPolyVertex, int& rnSecondPolyVertex ) const
{
	m_BrushFaces[idx]->MapEdgeIndexToPolyIndices( m_BrushVertices, m_BrushTriangles, nEdgeIndex, rnFirstPolyVertex, rnSecondPolyVertex );
}

size_t SBrush::GetNumberOfVertices() const
{
	return m_BrushVertices.size();
}


const Vec3& SBrush::GetVertexPos( int idx ) const
{
	assert( idx >= 0 && idx < (int)m_BrushVertices.size() );
	return m_BrushVertices[idx]->pos;
}

void SBrush::SetVertexPos( int idx, const Vec3& pos )
{
	assert( idx >= 0 && idx < (int)m_BrushVertices.size() );
	m_BrushVertices[idx]->pos = pos;
}

SBrushCommon::VertexFaceIndexType SBrush::GetFaceVertexIndex( int idx, int pidx ) const
{
	return m_BrushFaces[idx]->pointindexlist[pidx];
}


const SBrushPlane& SBrush::GetFacePlane( int idx ) const
{
	return m_BrushFaces[idx]->plane;
}


const AABB& SBrush::GetFaceBBox( int idx ) const
{
	return m_BrushFaces[idx]->boundbox;
}


void SBrush::SetVertexList( const std::vector<Vec3>& poslist )
{
	for( size_t i = 0; i < m_BrushVertices.size(); ++i )
	{
		delete m_BrushVertices[i];
	}
	m_BrushVertices.clear();	

	size_t vlistsize = poslist.size();

	for( size_t i = 0; i < vlistsize; ++i )
	{
		m_BrushVertices.push_back(new SBrushVertex(poslist[i]));
	}
}


void SBrush::AddFace( const std::vector<SBrushCommon::VertexFaceIndexType>& pointindexlist, 
											const SBrushCommon::STexInfo* texinfo, 
											const short* matID )
{
	SBrushFace* f = new SBrushFace;
	f->pointindexlist = pointindexlist;	
	
	if( texinfo )
		f->texinfo = *texinfo;

	if( matID )
		f->matID = *matID;

	m_BrushFaces.push_back(f);

	if( UpdateFromFace( static_cast<SBrushCommon::VertexFaceIndexType>(m_BrushFaces.size())-1 ) == false )
	{
		size_t index = m_BrushFaces.size()-1;
		SBrushFace* deletedface = m_BrushFaces[index];
		m_BrushFaces.erase( m_BrushFaces.begin() + index );
		delete deletedface;
	}
}


bool SBrush::UpdateFromFace( SBrushCommon::VertexFaceIndexType fidx )
{	
	SBrushFace * f = m_BrushFaces[fidx];

	size_t listsize = f->pointindexlist.size();
	std::vector<Vec3> poslist;
	for( size_t i = 0; i < listsize; ++i )
		poslist.push_back(m_BrushVertices[f->pointindexlist[i]]->pos);	

	SBrushCommon::VertexFaceIndexType triIndex[3] = { 0, 1, 2 };
	if( !FindTrianglePointsInPolygonForFace(poslist, triIndex[0], triIndex[1], triIndex[2] ) )
		return false;

	f->MakePlane( m_BrushVertices, triIndex[0], triIndex[1], triIndex[2] );
	f->CalcBound( m_BrushVertices );
	f->CalcCenter( m_BrushVertices );

	enum EInvalidTriangleType
	{
		eITT_Valid,
		eITT_Begining,
		eITT_Ending
	};

	EInvalidTriangleType invalidTriType = eITT_Valid;
	for( size_t i = 0; i < f->pointindexlist.size()-2; ++i )
	{
		SBrushTriangle tempTriangle;		
		if( tempTriangle.SetVertexIndices(	m_BrushVertices,
																				f->pointindexlist[0],
																				f->pointindexlist[i+1],
																				f->pointindexlist[i+2], fidx ) == true )
		{
			AddTriangle( f, tempTriangle );
			if( invalidTriType == eITT_Begining )
			{
				RemoveTriangle(f,m_BrushTriangles.size()-1);
				for( int k = 0; k < i+1; ++k )
				{
					if( tempTriangle.SetVertexIndices( m_BrushVertices, 
						f->pointindexlist[i+2],
						f->pointindexlist[k],
						f->pointindexlist[k+1], fidx ) )
					{
						AddTriangle( f, tempTriangle );
					}
					else
					{
						assert(0 && "Invalid Triangle in Solid Brush");
					}
				}
			}
		}
		else
		{
			float d0 = m_BrushVertices[f->pointindexlist[0]]->pos.GetDistance(m_BrushVertices[f->pointindexlist[i+1]]->pos);
			float d1 = m_BrushVertices[f->pointindexlist[0]]->pos.GetDistance(m_BrushVertices[f->pointindexlist[i+2]]->pos);
			if( d0 > d1 )
				invalidTriType = eITT_Ending;
			else
				invalidTriType = eITT_Begining;

			if( invalidTriType == eITT_Ending )
			{
				if( i+2 == f->pointindexlist.size()-1 )
				{
					assert(!m_BrushTriangles.empty());
					SBrushCommon::VertexFaceIndexType startIndex = 0;
					for( int k = 0; k < f->pointindexlist.size(); k++ )
					{
						if( f->pointindexlist[k] == m_BrushTriangles[m_BrushTriangles.size()-1]->vertexindices[1] )
						{
							startIndex = k;
							break;
						}
					}
					RemoveTriangle(f,m_BrushTriangles.size()-1);
					for( int k = startIndex+1; k < f->pointindexlist.size(); k++ )
					{
						if( tempTriangle.SetVertexIndices( m_BrushVertices, 
							f->pointindexlist[startIndex],
							f->pointindexlist[k],
							f->pointindexlist[(k+1)%f->pointindexlist.size()], fidx ) )
						{
							AddTriangle( f, tempTriangle );
						}
						else
						{
							assert(0 && "Invalid Triangle in Solid Brush");
						}
					}
				}
			}
		}
	}
	return true;
}


bool SBrush::FindTrianglePointsInPolygonForFace( 
	const std::vector<Vec3>& poslist, 																																						 
	SBrushCommon::VertexFaceIndexType& triIndex0, 
	SBrushCommon::VertexFaceIndexType& triIndex1, 
	SBrushCommon::VertexFaceIndexType& triIndex2  )
{
	const float SameDirectionStandard = 0.99999f;

	size_t listsize = poslist.size();
	int entryIdx = SBrushCommon::VertexFaceMax;	

	for( size_t j = 0; j < listsize-2; ++j )
	{
		Vec3 v0 = poslist[0];
		Vec3 v1 = poslist[j+1];
		Vec3 v2 = poslist[j+2];

		Vec3 v01 = (v1-v0).GetNormalized();
		Vec3 v02 = (v2-v0).GetNormalized();
		float dotV01V02 = v01.Dot(v02);

		if( dotV01V02 < SameDirectionStandard )
		{	
			triIndex0 = 0;
			triIndex1 = j+1;
			triIndex2 = j+2;
			return true;
		}
	}

	return false;
}


void SBrush::BackupBrush( SBackupBrushInfo& BackupInfo )
{
	for( size_t i = 0; i < m_BrushVertices.size(); ++i )
		BackupInfo.m_Vertices.push_back( new SBrushVertex( *m_BrushVertices[i] ) );

	for( size_t i = 0; i < m_BrushTriangles.size(); ++i )
		BackupInfo.m_Triangles.push_back( new SBrushTriangle( *m_BrushTriangles[i] ) );

	for( size_t i = 0; i < m_BrushFaces.size(); ++i )
		BackupInfo.m_Faces.push_back( new SBrushFace( *m_BrushFaces[i] ) );
}


void SBrush::RestoreBrush(	SBackupBrushInfo& BackupInfo )
{
	for( size_t i = 0; i < m_BrushVertices.size(); ++i )
	{
		if( m_BrushVertices[i] )
			delete m_BrushVertices[i];
	}

	for( size_t i = 0; i < m_BrushTriangles.size(); ++i )
	{
		if( m_BrushTriangles[i] )
			delete m_BrushTriangles[i];
	}

	for( size_t i = 0; i < m_BrushFaces.size(); ++i )
	{
		if( m_BrushFaces[i] )
			delete m_BrushFaces[i];
	}

	m_BrushVertices		= BackupInfo.m_Vertices;
	m_BrushTriangles	= BackupInfo.m_Triangles;
	m_BrushFaces			= BackupInfo.m_Faces;

	BackupInfo.m_Vertices.clear();
	BackupInfo.m_Triangles.clear();
	BackupInfo.m_Faces.clear();
}


SBrush::SBackupBrushInfo::~SBackupBrushInfo()
{
	for( size_t i = 0; i < m_Vertices.size(); ++i )
		delete m_Vertices[i];

	for( size_t i = 0; i < m_Triangles.size(); ++i )
		delete m_Triangles[i];

	for( size_t i = 0;i  < m_Faces.size(); ++i )
		delete m_Faces[i];
}


bool SBrush::IsConvexHull() const
{
	for( size_t i = 0; i < m_BrushFaces.size(); ++i )
	{
		SBrushFace* baseface = m_BrushFaces[i];
		SBrushTriangle* triangle = m_BrushTriangles[baseface->triangleidxlist[0]];

		Vec3 v[3] = {	m_BrushVertices[triangle->vertexindices[0]]->pos,
									m_BrushVertices[triangle->vertexindices[1]]->pos,
									m_BrushVertices[triangle->vertexindices[2]]->pos };

		SBrushPlane p_base(v[0],v[1],v[2]);

		for( size_t j = 0; j < m_BrushFaces.size(); ++j )
		{
			if( i == j )
				continue;

			SBrushFace* face = m_BrushFaces[j];

			for( size_t k = 0; k < face->pointindexlist.size(); ++k )
			{
				SBrushVertex* vertex = m_BrushVertices[face->pointindexlist[k]];
				if( p_base.Distance(vertex->pos) > VER_EPS )
					return false;
			}
		}
	}
	return true;
}


void SBrush::PivotToCenter( Vec3* newPivot )
{
	Vec3 RelativePivot = m_bounds.GetCenter();

	for( size_t i = 0; i < m_BrushVertices.size(); ++i )
		m_BrushVertices[i]->pos -= RelativePivot;

	m_bounds.min -= RelativePivot;
	m_bounds.max -= RelativePivot;

	if( newPivot )
		*newPivot = GetMatrix().GetTranslation() + RelativePivot;
}


void SBrush::SetMatrix( const Matrix34 &tm, bool Transfer2Owner )
{
	m_matrix = tm;
	if( m_Owner && Transfer2Owner )	
		m_Owner->SetWorldTM(tm);
}


void SBrush::Create( const Vec3 &mins,const Vec3& maxs,int numSides, SBrushCommon::ESolidBrushCreateType shapetype )
{
	assert( shapetype >= SBrushCommon::eBrushCreateType_Box && shapetype < SBrushCommon::eBrushCreateType_Max );
	assert( numSides >= 3 );

	ClearFaces();
	CBrushPrimitive BrushPrimitive;

	if( shapetype == SBrushCommon::eBrushCreateType_Box )
	{
		BrushPrimitive.CreateBox( this, mins, maxs );
	}
	else if( shapetype == SBrushCommon::eBrushCreateType_Cone )
	{
		BrushPrimitive.CreateCone( this, mins, maxs, numSides );
	}
	else if( shapetype == SBrushCommon::eBrushCreateType_Sphere )
	{
		BrushPrimitive.CreateSphere( this, mins, maxs, numSides );
	}
	else if( shapetype == SBrushCommon::eBrushCreateType_Cylinder )
	{
		BrushPrimitive.CreateCylinder( this, mins, maxs, numSides );
	}	
	else if( shapetype == SBrushCommon::eBrushCreateType_Plane )
	{
		BrushPrimitive.CreatePlane( this, mins, maxs );
	}	

	BuildBrush(true,true);
}


void SBrush::CreateSimpleMesh(const std::vector<Vec3>& vtxs, const float height)
{
	ClearFaces();
	CBrushPrimitive BrushPrimitive;
	BrushPrimitive.CreateSimpleMesh( this, vtxs, height );
	BuildBrush(true,true);	
}


SBrushTriangle* SBrush::AddTriangle()
{
	SBrushTriangle* triangle = new SBrushTriangle;
	m_BrushTriangles.push_back(triangle);
	return triangle;
}


SBrushTriangle* SBrush::AddTriangle(	SBrushCommon::VertexFaceIndexType vertexindex0, 
																			SBrushCommon::VertexFaceIndexType vertexindex1, 
																			SBrushCommon::VertexFaceIndexType vertexindex2, 
																			SBrushCommon::VertexFaceIndexType faceindex)
{
	SBrushTriangle triangle;
	if( triangle.SetVertexIndices( m_BrushVertices, vertexindex0, vertexindex1, vertexindex2, faceindex ) == true )
	{
		SBrushTriangle* triobj = new SBrushTriangle(triangle);
		m_BrushTriangles.push_back(triobj);
		return triobj;
	}
	return NULL;
}


SBrushTriangle* SBrush::AddTriangle(	const Vec3& v0, const Vec3& v1, const Vec3& v2, 
																			SBrushCommon::VertexFaceIndexType i0, 
																			SBrushCommon::VertexFaceIndexType i1, 
																			SBrushCommon::VertexFaceIndexType i2, 
																			SBrushCommon::VertexFaceIndexType fidx)
{
	SBrushTriangle triangle;
	if( triangle.SetVertexIndices( v0, v1, v2, i0, i1, i2, fidx ) == true )
	{
		SBrushTriangle* triobj = new SBrushTriangle(triangle);
		m_BrushTriangles.push_back(triobj);
		return triobj;
	}
	return NULL;
}

void SBrush::AddTriangle( SBrushFace* face, const SBrushTriangle& triangle )
{	
	m_BrushTriangles.push_back(new SBrushTriangle(triangle));
	face->triangleidxlist.push_back((SBrushCommon::VertexFaceIndexType)m_BrushTriangles.size()-1);
}

void SBrush::RemoveTriangle( SBrushFace* face, int index )
{
	if( index >= 0 && index < m_BrushTriangles.size() )
	{
		delete m_BrushTriangles[index];
		m_BrushTriangles.erase( m_BrushTriangles.begin() + index );
		for( int i = 0, iCount = face->triangleidxlist.size(); i < iCount; ++i )
		{
			if( face->pointindexlist[i] == index )
			{
				face->triangleidxlist.erase( face->triangleidxlist.begin() + i );
				break;
			}
		}
	}
}

SBrushVertex* SBrush::AddEmptyVertex()
{
	if( m_BrushVertices.size() >= SBrushCommon::VertexFaceMax-1 )
		return NULL;
	SBrushVertex* vertex = new SBrushVertex;
	m_BrushVertices.push_back(vertex);
	return vertex;
}


SBrushVertex* SBrush::AddVertex( const Vec3& pos )
{
	if( m_BrushVertices.size() >= SBrushCommon::VertexFaceMax-1 )
		return NULL;
	SBrushVertex* vertex = new SBrushVertex(pos);
	m_BrushVertices.push_back(vertex);
	return vertex;
}


void SBrush::ExcludeInvalidData()
{
	RemoveDuplicatedVerticesInFace();
	MakeInvalidTriangleWithVerySmallAreaNullPointer();
	DeleteInvalidTrianglesInFace();
	MakeInvalidTriangleWithInvalidFaceNullPointer();

	std::vector<SBrushTriangle*> newTriangleList;
	std::vector<SBrushFace*> newFaceList;
	std::map<int,int> triangleMapper;
	std::map<int,int> faceMapper;

	newTriangleList.reserve(m_BrushTriangles.size());
	newFaceList.reserve(m_BrushFaces.size());

	MakeNewListAndMapperForCreatingNewValidList( m_BrushTriangles, newTriangleList, triangleMapper );
	MakeNewListAndMapperForCreatingNewValidList( m_BrushFaces, newFaceList, faceMapper );

	MapOldFaceIndexToNewFaceIndexInTriangleList( newTriangleList, faceMapper );
	MapOldTriangleIndexToNewTriangleIndexInFaceList( newFaceList, triangleMapper );

	m_BrushTriangles = newTriangleList;
	m_BrushFaces = newFaceList;
}

void SBrush::RemoveDuplicatedVerticesInFace()
{
	for( int i = 0, iFaceSize(m_BrushFaces.size()); i < iFaceSize; ++i )
	{
		SBrushFace* pFace = m_BrushFaces[i];
		bool bValidFace = true;

		if( pFace->pointindexlist.empty() )
		{
			bValidFace = false;
		}
		else
		{
			std::set<int> InvalidPoints;
			for( int k = 0, iPointSize(pFace->pointindexlist.size()); k < iPointSize; ++k )
			{
				if( InvalidPoints.find(k) != InvalidPoints.end() )
					continue;
				int currentIndex = pFace->pointindexlist[k];
				for( int a = k+1; a < iPointSize; ++a )
				{
					if (InvalidPoints.find(a) != InvalidPoints.end())
						continue;
					int followingIndex = pFace->pointindexlist[a];
					if ((m_BrushVertices[currentIndex]->pos-m_BrushVertices[followingIndex]->pos).IsZero(0.0001f) == true)
					{
						InvalidPoints.insert(a);
						break;
					}
				}
			}

			if (!InvalidPoints.empty())
			{
				std::vector<SBrushCommon::VertexFaceIndexType> newPointList;
				newPointList.reserve(pFace->pointindexlist.size());

				for( int k = 0, iPointSize(pFace->pointindexlist.size()); k < iPointSize; ++k )
				{
					if (InvalidPoints.find(k) == InvalidPoints.end())
						newPointList.push_back( pFace->pointindexlist[k] );
				}

				pFace->pointindexlist = newPointList;
			}

			if( pFace->pointindexlist.empty() )
				bValidFace = false;
		}

		if (!bValidFace)
		{
			delete m_BrushFaces[i];
			m_BrushFaces[i] = NULL;
		}
	}
}

void SBrush::MakeInvalidTriangleWithVerySmallAreaNullPointer()
{
	for( int i = 0, iSize(m_BrushTriangles.size()); i < iSize; ++i )
	{
		SBrushTriangle* pTriangle = m_BrushTriangles[i];

		Vec3 v0(m_BrushVertices[pTriangle->vertexindices[1]]->pos-m_BrushVertices[pTriangle->vertexindices[0]]->pos);
		Vec3 v1(m_BrushVertices[pTriangle->vertexindices[2]]->pos-m_BrushVertices[pTriangle->vertexindices[0]]->pos);
		float areaOfTriangle(v0.Cross(v1).GetLength());

		if( areaOfTriangle < 0.0001f )
		{
			delete m_BrushTriangles[i];
			m_BrushTriangles[i] = NULL;
		}
	}
}

void SBrush::DeleteInvalidTrianglesInFace()
{
	for( int i = 0, iSize(m_BrushFaces. size()); i < iSize; ++i )
	{
		SBrushFace* pFace = m_BrushFaces[i];

		if( pFace == NULL )
			continue;

		std::vector<SBrushCommon::VertexFaceIndexType>::iterator ii = pFace->triangleidxlist.begin();
		for(; ii != pFace->triangleidxlist.end(); )
		{
			if( m_BrushTriangles[*ii] == NULL )
				ii = pFace->triangleidxlist.erase(ii);			
			else
				++ii;
		}

		if( pFace->triangleidxlist.empty() )
		{
			delete m_BrushFaces[i];
			m_BrushFaces[i] = NULL;
		}
	}
}

void SBrush::MakeInvalidTriangleWithInvalidFaceNullPointer()
{
	for( int i = 0, iTriSize(m_BrushTriangles.size()); i < iTriSize; ++i )
	{
		SBrushTriangle* pTriangle = m_BrushTriangles[i];

		if( pTriangle == NULL )
			continue;

		bool bValid = true;
		if( pTriangle->faceidx < 0 || pTriangle->faceidx >= m_BrushFaces.size() )
			bValid = false;
		else if( m_BrushFaces[pTriangle->faceidx] == NULL )
			bValid = false;

		if( !bValid )
		{
			delete m_BrushTriangles[i];
			m_BrushTriangles[i] = NULL;
		}
	}
}

template<typename T>
void SBrush::MakeNewListAndMapperForCreatingNewValidList( std::vector<T>& inputList, std::vector<T>& outList, std::map<int,int>& outMapper )
{
	outList.reserve(inputList.size());

	for( int i = 0, iSize(inputList. size()); i < iSize; ++i )
	{
		if( inputList[i] )
		{
			outMapper[i] = outList.size();
			outList.push_back(inputList[i]);
		}
	}
}

void SBrush::MapOldFaceIndexToNewFaceIndexInTriangleList( std::vector<SBrushTriangle*>& triangleList, std::map<int,int>& faceMapper )
{
	for( int i = 0, iTriSize(triangleList.size()); i < iTriSize; ++i )
	{
		SBrushTriangle* pTriangle = triangleList[i];
		assert(pTriangle);		
		assert(faceMapper.find(pTriangle->faceidx) != faceMapper.end() );
		pTriangle->faceidx = faceMapper[pTriangle->faceidx];
	}
}

void SBrush::MapOldTriangleIndexToNewTriangleIndexInFaceList( std::vector<SBrushFace*>& faceList, std::map<int,int>& triangleMapper )
{
	for( int i = 0, iFaceSize(faceList.size()); i < iFaceSize; ++i )
	{
		SBrushFace* pFace = faceList[i];
		assert(pFace);
		for( int k = 0, iTriSize(pFace->triangleidxlist.size()); k < iTriSize; ++k )
		{
			assert( triangleMapper.find(pFace->triangleidxlist[k]) != triangleMapper.end() );
			pFace->triangleidxlist[k] = triangleMapper[pFace->triangleidxlist[k]];
		}
	}
}